// @algorithm @lc id=79 lang=cpp 
// @title word-search


// @test([["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]],"ABCCED")=true
// @test([["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]],"SEE")=true
// @test([["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]],"ABCB")=false
using it_t = string::iterator;
class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        int m = board.size(), n = board[0].size();
        // 字典 char => (i,j)
        unordered_map< char,vector<pair<int,int>> > dict;
        for(int i=0; i<m; i++)
            for(int j=0; j<n; j++)
                dict[board[i][j]].push_back({i,j});

        // 记忆化搜索 每个位置(i,j)的字符不重复使用
        vector<vector<bool>> used(m, vector<bool>(n, false));
        function<bool(int,int,it_t)> dfs = [&](int i, int j, it_t letter)->bool{
            if(letter == word.end()) return true;
            auto it = dict.find(*letter);
            if(it == dict.end()) return false;
            for(auto &[x,y] : it->second){
                if(used[x][y] || (0<=i && abs(x-i)+abs(y-j)!=1))
                    continue;
                used[x][y] = true;
                if(dfs(x, y, letter+1)) return true;
                used[x][y] = false;
            }
            return false;
        };
        return dfs(-1, -1, word.begin());
    }
};